package com.xinxin.leetcode.problem501;

import com.xinxin.leetcode.common.TreeNode;
import com.xinxin.leetcode.common.TreeUtil;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author ShiXinXin
 * @date 2020-01-08 10:15
 */
class Solution {
    private int preVal = 0, curTimes = 0, maxTimes = 0;
    private ArrayList<Integer> list = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        traversal(root);
        //list转换为int[]
        int size = list.size();
        int[] ans = new int[size];
        for (int i = 0; i < size; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    //二叉搜索树中序遍历是递增顺序
    private void traversal(TreeNode root) {
        if (root != null) {
            traversal(root.left);
            //判断当前值与上一个值的关系, 更新 curTimes 和 preVal
            if (preVal == root.val) {
                curTimes++;
            } else {
                preVal = root.val;
                curTimes = 1;
            }
            //判断当前数量与最大数量的关系, 更新 list 和 maxTimes
            if (curTimes == maxTimes) {
                list.add(root.val);
            } else if (curTimes > maxTimes) {
                list.clear();
                list.add(root.val);
                maxTimes = curTimes;
            }
            traversal(root.right);
        }
    }

    public static void main(String[] args) {
        TreeNode tree = TreeUtil.createTree(new int[]{1, 0, 2, 2, 0, 0, 0});
        System.out.println(Arrays.toString(new Solution().findMode(tree)));
    }
}
